//第一种方法：
class Solution {
public:
    std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
        std::unordered_map<int, int> cnt;
        for (int num : nums) {
            cnt[num]++;
        }
 
        // 将 unordered_map 转换为 vector 并排序
        std::vector<std::pair<int, int>> freq_vec(cnt.begin(), cnt.end());
        std::sort(freq_vec.begin(), freq_vec.end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
            return a.second > b.second; // 按频率从高到低排序
        });
 
        std::vector<int> ret;
        for (int i = 0; i < k; ++i) {
            ret.push_back(freq_vec[i].first);
        }
        return ret;
    }
};
//第二种方法：
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        for (int num : nums) {
            cnt[num]++;
        }
 
        // 使用最大堆（优先级队列）来存储频率最高的 k 个元素
        auto cmp = [](pair<int, int>& a, pair<int, int>& b) {
            return a.second > b.second; // 注意这里是小于号，因为我们希望这是一个最小堆
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
 
        for (auto& e : cnt) {
            q.push(e);
            if (q.size() > k) {
                q.pop(); // 弹出频率最低的元素（在最小堆中堆顶是频率最小的，但因为我们只保留 k 个，所以超过 k 个时要弹出的是新加入的且频率相对较大的元素）
            }
        }
 
        vector<int> ret;
        while (!q.empty()) {
            ret.push_back(q.top().first);
            q.pop();
        }

 
        return ret;
    }
};